package basic.courseLearn11.problem;

import basic.courseLearn11.UnionFindSet;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Objects;

//岛问题，求连通的岛屿数量
public class IslandNum {

    private class Location{
        int x;
        int y;
        public Location(int x,int y){
            this.x = x;
            this.y = y;
        }
        public Location(){}

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Location)) return false;
            Location location = (Location) o;
            return x == location.x && y == location.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }


    /**
     * 求连通的岛屿数量
     * @param nums 二维数组
     * @param m x轴长度
     * @param n y轴长度
     * @return 连通的岛屿数量
     */
    public int numIslands(int[][] nums,int m,int n) {
        //1.定义岛屿数目
        int num = 0;
        //2.遍历二维数组
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                //2.1.1 判断该位置是否为岛屿
                if(nums[i][j]==1){
                    infect(nums,m,n,i,j);
                    num++;
                }
            }
        }
        //3.返回岛屿数目
        return num;
    }

    /**
     * 求连通的岛屿数量-多线程
     * @param nums 二维数组
     * @param m x轴长度
     * @param n y轴长度
     * @return 连通的岛屿数量
     * @param split_x 切分的x轴坐标
     */
    public int numIslands(int[][] nums,int m,int n,int split_x) {
        //0.初始化并查集
        UnionFindSet unionFindSet = new UnionFindSet();
        ArrayList<Location> list = new ArrayList<>();
        unionFindSet.initSet(list);
        //1.定义岛屿数目
        int num_1 = 0,num_2 = 0;
        //2.遍历二维数组--第一部分0-split_x
        for(int i=0;i<n;i++){
            for(int j=0;j<m-split_x;j++){
                //2.1.1 判断该位置是否为岛屿
                if(nums[i][j]==1){
                    Location location = new Location(i,j);
                    if (j!=split_x-1){
                        unionFindSet.addElement(location);
                    }
                    infect(nums,0,m-split_x,n,i,j,unionFindSet,location);
                    num_1++;
                }
            }
        }
        System.out.println("左侧部分岛屿数目："+num_1);
        //3.遍历二维数组--第二部分split_x-m
        for(int i=0;i<n;i++){
            for(int j=split_x;j<m;j++){
                //2.1.1 判断该位置是否为岛屿
                if(nums[i][j]==1){
                    Location location = new Location(i,j);
                    if (j!=split_x){
                        unionFindSet.addElement(location);
                    }
                    infect(nums,split_x,m,n,i,j,unionFindSet,location);
                    num_2++;
                }
            }
        }
        System.out.println("右侧部分岛屿数目："+num_2);
        //4.返回岛屿数目
        return union(nums,split_x,n,num_1+num_2,unionFindSet);
    }

    private int union(int[][] nums, int splitX, int n, int count, UnionFindSet unionFindSet) {

        //1.逐个遍历中间区域的岛屿
        for(int i=0;i<n;i++){
            int j = splitX-1;
            //1.2 两侧都为1
            if(nums[i][j]==2 && nums[i][j+1]==2){
                //1.2.1 判断两侧的集合是否相连
                if (!unionFindSet.isSameSet(new Location(i,j),new Location(i,j+1))){
                    count--;
                    unionFindSet.unionSet(new Location(i,j),new Location(i,j+1));
                }
            }
        }


        return count;
    }


    /**
     * 传染过程，将该位置及其相邻的位置变为2，表示已经访问过
     * @param nums 二维数组
     * @param m x轴长度
     * @param n y轴长度
     * @param i x轴坐标
     * @param j y轴坐标
     */
    private void infect(int[][] nums, int m, int n, int i, int j) {

        // 1.判断是否超出边界，或者不为1，则直接返回
        if (i < 0 || i >= n || j < 0 || j >= m || nums[i][j]!= 1) {
            return;
        }
        // 2. 将该位置变为2，表示已经访问过
        nums[i][j] = 2;
        // 3. 传染
        infect(nums, m, n, i + 1, j);
        infect(nums, m, n, i - 1, j);
        infect(nums, m, n, i, j + 1);
        infect(nums, m, n, i, j - 1);

    }

    /**
     * 传染过程，--多线程
     * @param nums 二维数组
     * @param m_start x坐标边界-左侧
     * @param m_end x坐标边界-右侧
     * @param n y轴长度
     * @param i x轴坐标
     * @param j y轴坐标
     */
    private void infect(int[][] nums, int m_start, int m_end, int n, int i, int j,UnionFindSet unionFindSet,Location location) {

        // 1.判断是否超出边界，或者不为1，则直接返回
        if (i < 0 || i >= n || j < m_start || j >= m_end || nums[i][j]!= 1) {
            return;
        }
        // 2. 将该位置变为2，表示已经访问过
        nums[i][j] = 2;
        // 3. 如果处于边界位置，存储到并查集中
        if(m_start==0 && j==m_end-1){
            Location new_location = new Location(i,j);
            unionFindSet.addElement(new_location);
            unionFindSet.unionSet(location,new_location);
        }
        if (m_start!= 0 && j == m_start){
            Location new_location = new Location(i,j);
            unionFindSet.addElement(new_location);
            unionFindSet.unionSet(location,new_location);
        }
        // 3. 传染
        infect(nums, m_start, m_end, n, i + 1, j ,unionFindSet,location);
        infect(nums,  m_start, m_end, n, i - 1, j,unionFindSet,location);
        infect(nums,  m_start, m_end, n, i, j + 1,unionFindSet,location);
        infect(nums,  m_start, m_end, n, i, j - 1,unionFindSet,location);

    }

    @Test
    public void test_1(){
        int[][] nums = {{0,0,1,0,1,0},
                        {1,1,1,0,1,0},
                        {1,0,0,1,0,0},
                        {0,0,0,0,0,0},};
        int m = 6;
        int n = 4;
        int num = numIslands(nums,m,n);
        System.out.println(num); // 3
    }

    @Test
    public void test_2(){
        int[][] nums = {{1,1,1,1,1,1},
                        {1,0,0,0,1,1},
                        {1,0,1,1,1,0},
                        {1,0,1,0,1,0},
                        {1,0,0,0,0,1},
                        {1,1,1,1,1,1}
        };
        int m_total = 6;
        int n_total = 6;
        int num = numIslands(nums,m_total,n_total);
        System.out.println("total islands: "+num); // 1
        int split_x = 3;
        nums = new int[][]{{1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 1, 1},
                {1, 0, 1, 1, 1, 0},
                {1, 0, 1, 0, 1, 0},
                {1, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1}
        };
        int num_split = numIslands(nums,m_total,n_total,split_x);
        System.out.println("split islands: "+num_split); // 2


    }


}
